#include <iostream>
#include <deque>
#include <vector>
#include <stdexcept>
#include <stlhelper.h>
#include <boost/format.hpp>
#include <utility>
#include <single_linkage.h>
#include <portable_timer.h>
#include <progress_indicator.h>
#include <stdlib.h>

using namespace std;
using boost::format;

unsigned EVAL_LIMIT = 200;
unsigned int ARR_SIZE = 20;
unsigned int CNT_PAIRS = 3;
//unsigned int ARR_SIZE = 200000;
//unsigned int CNT_PAIRS = unsigned(ARR_SIZE*0.53);

void evaluate(std::deque<std::vector<unsigned> >& clusters)
{
	unsigned total = 0;
	double cluster_size = 0;
	unsigned max_cluster_size = 0;
	deque<unsigned> cnts(ARR_SIZE, 0);
	for (unsigned ii = 0; ii < clusters.size(); ++ii)
	{
		max_cluster_size = std::max(max_cluster_size, clusters[ii].size());
		cluster_size += clusters[ii].size();
		for (unsigned jj = 0; jj < clusters[ii].size(); ++jj)
		{
			assert(clusters[ii][jj] < cnts.size());
			++cnts[clusters[ii][jj]];
			total++;
		}
	}
	if (ARR_SIZE <= EVAL_LIMIT)
	{
		for (unsigned ii = 0; ii < clusters.size(); ++ii)
		{
			cerr << "># " << ii << "\t";
			for (unsigned jj = 0; jj < clusters[ii].size(); ++jj)
				cerr << clusters[ii][jj] << ",";
			cerr << "\n";
		}
	}

	unsigned cnt_hits = 0;
	unsigned cnt_doubles = 0;
	for (unsigned i = 0; i < cnts.size(); ++i)
	{
		if (cnts[i])
			++cnt_hits;
		if (cnts[i] > 1)
			++cnt_doubles;
	}
	cerr << "total = " << total << "\n";
	if (cnt_doubles != 0)
		throw std::logic_error("Same index in more than one group\n");
	cerr << "Num of clusters = " << clusters.size() << "\n";
	cerr << "average clusters size = " << cluster_size / clusters.size() << "\n";
	cerr << "max clusters size = " << max_cluster_size << "\n";
}


//________________________________________________________________________________________

//	sort deque of unsigned by size then by index of first element

//________________________________________________________________________________________
struct op_sort_deque_u_by_size
{
	bool operator ()( vector<unsigned>& a, vector<unsigned>& b) const
	{
		if (a.size() != b.size())
			return a.size() < b.size();
		if (a.size() == 0)
			return false;
		return a[0] < b[0];
	}
};

//________________________________________________________________________________________

//	slow_single_linkage_clusters

//		The performance of this function degrades badly with large clusters
//				because when clusters are merged, each member has to be repointed
//				to the new cluster


//		included here mainly to compare with single_linkage_clusters

//________________________________________________________________________________________
void slow_single_linkage_clusters(   const deque<pair<unsigned, unsigned> >&	pairs,
										deque<vector<unsigned> >&				clusters,
										t_progress_indicator& 					dots)
{
	//// NB cluster_ids start from 1: zero = unassigned cluster
	deque<unsigned>				id_to_cluster;
	deque<vector<unsigned>* >	id_clusters;
	id_clusters.push_back(new vector<unsigned>);
	unsigned					cnt_clusters = 0;

	for (unsigned ii = 0; ii < pairs.size(); ++ii)
	{
		++dots;
		unsigned id1 = pairs[ii].first;
		unsigned id2 = pairs[ii].second;
		if (id1 == id2)
			continue;
		//DEBUG cerr << "\tpair = " << id1 << "," << id2 << "\n";

		// expand id_to_cluster if necessary
		unsigned max_id = std::max(id1, id2);
		if (max_id >= id_to_cluster.size())
		{
			id_to_cluster.insert(id_to_cluster.end(), max_id - id_to_cluster.size() + 1, 0);
			//DEBUG cerr  << "expand id_to_cluster to " << max_id << "\n";
		}

		unsigned& curr_cluster1 = id_to_cluster[id1];
		unsigned& curr_cluster2 = id_to_cluster[id2];

		// add new cluster if neither is yet clustered
		if (curr_cluster1 + curr_cluster2 == 0)
		{
			// cluster index for these two ids
			curr_cluster1 =
			curr_cluster2 = ++cnt_clusters;

			// these two ids make up a new cluster
			id_clusters.push_back(new vector<unsigned>());
			id_clusters.back()->push_back(id1);
			id_clusters.back()->push_back(id2);
			//DEBUG cerr << "Add new cluster id  " << cnt_clusters << " for " << id1 << " and " << id2 << "\n";
			//DEBUG cerr << "Cluster " << cnt_clusters << " contains :";
			//DEBUG for (unsigned i = 0; i < id_clusters[cnt_clusters].size(); ++i)
			//DEBUG 	cerr << id_clusters[cnt_clusters][i] << ",";
			//DEBUG cerr << "\n";
		}

		// link cluster 2 to cluster 1 if both already have clusters
		else if (curr_cluster1 && curr_cluster2)
		{
			// ignore if both already part of the same cluster
			if (curr_cluster1 == curr_cluster2)
			{
				//DEBUG cerr << "Same cluster " << curr_cluster2 << " \n";
				continue;
			}

			// assign curr_cluster1 to all of curr_cluster2 ids;
			std::sort(id_clusters[curr_cluster2]->begin(), id_clusters[curr_cluster2]->end());
			vector<unsigned>::iterator ids_end = std::unique(id_clusters[curr_cluster2]->begin(),
															id_clusters[curr_cluster2]->end());

			vector<unsigned>::iterator ids_iter = id_clusters[curr_cluster2]->begin();
			unsigned old_cluster = curr_cluster2;
			while (ids_iter != ids_end)
				id_to_cluster[*ids_iter++] = curr_cluster1;

			// merge cluster 2 into cluster 1

			id_clusters[curr_cluster1]->insert(id_clusters[curr_cluster1]->end(),
												id_clusters[old_cluster]->begin(),
												ids_end);
			//id_clusters[old_cluster].clear();
			delete id_clusters[old_cluster];
			id_clusters[old_cluster] = 0;
			//DEBUG cerr << "Merge cluster " << old_cluster <<  " into cluster " << curr_cluster1 << "\n";
			//DEBUG cerr << "Cluster " << curr_cluster1 << " contains :";
			//DEBUG for (unsigned i = 0; i < id_clusters[curr_cluster1].size(); ++i)
			//DEBUG 	cerr << id_clusters[curr_cluster1][i] << ",";
			//DEBUG cerr << "\n";
		}

		// add id 2 to cluster 1 if id 2 is unclustered
		else if (curr_cluster1)
		{
			id_clusters[curr_cluster2 = curr_cluster1]->push_back(id2);
			//DEBUG cerr << "Add " << id2 <<" to cluster " << curr_cluster1 << "\n";
			//DEBUG cerr << "Cluster " << curr_cluster1 << " contains :";
			//DEBUG for (unsigned i = 0; i < id_clusters[curr_cluster1].size(); ++i)
			//DEBUG 	cerr << id_clusters[curr_cluster1][i] << ",";
			//DEBUG cerr << "\n";
		}

		// add id 1 to cluster 2 if id 1 is unclustered
		else
		{
			id_clusters[curr_cluster1 = curr_cluster2]->push_back(id1);
			//DEBUG cerr << "Add " << id1 <<" to cluster " << curr_cluster1 << "\n";
			//DEBUG cerr << "Cluster " << curr_cluster1 << " contains :";
			//DEBUG for (unsigned i = 0; i < id_clusters[curr_cluster1].size(); ++i)
			//DEBUG 	cerr << id_clusters[curr_cluster1][i] << ",";
			//DEBUG cerr << "\n";
		}
	}

	//dots.print_indicator("!");
	//
	// copy non-empty clusters to output set
	//
	for (unsigned i = 0; i < id_clusters.size(); ++i)
		if (id_clusters[i] && !id_clusters[i]->empty())
		{
			std::sort(id_clusters[i]->begin(),  id_clusters[i]->end());

			clusters.push_back(vector<unsigned>(id_clusters[i]->begin(),
								   			   	std::unique(id_clusters[i]->begin(),
															id_clusters[i]->end())));
			delete id_clusters[i];
			id_clusters[i] = 0;
		}
	// sort output clusters by size and then index of first id
	sort_with_swaps(clusters, op_sort_deque_u_by_size());
}

int main (int argc, char *argv[])
{
	// initialize pairs
	deque<pair<unsigned,  unsigned> > pairs;
	for (unsigned i = 0; i < CNT_PAIRS; ++i)
		pairs.push_back(pair<unsigned,  unsigned>(rand() % ARR_SIZE, rand() % ARR_SIZE));

	if (ARR_SIZE <= 20)
	{
		for (unsigned i = 0; i < pairs.size(); ++i)
			cerr << format("%1$+5d\t%2$+5d\n") % pairs[i].first % pairs[i].second;
			//cerr << pairs[i].first << "," << pairs[i].second << "\n";
		cerr << "\n\n";
	}

	std::deque<std::vector<unsigned> > fast_clusters;
	{
		t_portable_timer timer;
		t_progress_indicator	dots(cerr, 20000);
		single_linkage_clusters(pairs, fast_clusters, dots);
		dots.finish();
		cerr << timer.pretty_reset() << "\n";
		evaluate(fast_clusters);
	}
	std::deque<std::vector<unsigned> > slow_clusters;
	{
		t_portable_timer timer;
		t_progress_indicator	dots(cerr, 20000);
		slow_single_linkage_clusters(pairs, slow_clusters, dots);
		dots.finish();
		cerr << timer.pretty_reset() << "\n";
		evaluate(slow_clusters);
	}

	if(slow_clusters != fast_clusters)
		throw std::runtime_error("\n\n\n" + string(80, '8') +
								"\n\nClusters are not the same.!!!!\n\n" +
								string(80, '8') + "\n");
	cerr << "\nSuccess!\nClusters are the same.\n";
	return 0;
}

